class Solution {
public:


    bool Find(stack<TreeNode*>& st, TreeNode* root, TreeNode* aim)
    {
        if (root == nullptr)
            return false;

        st.push(root);


        if (root == aim)
            return true;

        if (Find(st, root->left, aim))
            return true;

        if (Find(st, root->right, aim))
            return true;


        st.pop();
        return false;
    }


    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        if (root == nullptr)
            return root;


        stack<TreeNode*> st1;
        stack<TreeNode*> st2;


        Find(st1, root, p);
        Find(st2, root, q);


        while (st1.size() > st2.size())
            st1.pop();

        while (st2.size() > st1.size())
            st2.pop();


        while (st1.top() != st2.top())
        {
            st1.pop();
            st2.pop();
        }


        return st1.top();
    }
};
